package Test04;

import java.util.Scanner;

public class 插入 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            int[] sortedArr = insertionSort(arr); // 调用插入排序算法
            for (int i = 0; i < n; i++) {
                System.out.print(sortedArr[i] + " ");
            }
        }

        public static int[] insertionSort(int[] arr) {
            int n = arr.length;
            for (int i = 1; i < n; i++) {
                int key = arr[i];
                int j = i - 1;
                while (j >= 0 && arr[j] > key) {
                    arr[j+1] = arr[j];
                    j--;
                }
                arr[j+1] = key;
            }
            return arr;
        }
    }

